%%%-------------------------------------------------------------------
%%% File    : p14.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% The following iterative sequence is defined for the set of positive integers:
%%% n → n/2 (n is even)
%%% n → 3n + 1 (n is odd)
%%% Using the rule above and starting with 13, we generate the following sequence:
%%% 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
%%% It can be seen that this sequence (starting at 13 and finishing at 1) contains 
%%% 10 terms. Although it has not been proved yet (Collatz Problem), it is thought 
%%% that all starting numbers finish at 1.
%%% Which starting number, under one million, produces the longest chain?
%%% NOTE: Once the chain starts the terms are allowed to go above one million.
%%%
%%% Created :  4 Dec 2008
%%%-------------------------------------------------------------------
-module(p14).

-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: solution(Max) -> {N, ChainLength}
%% Description: Returns the number bellow Max that has the longest 
%% chain length
%%
%%--------------------------------------------------------------------
solution(Max) ->
    iterate(2, Max, 1, 0, ets:new(lookup, [])).

% Just calculate all chain lengths, but
% use a lookup table to save calculations for previous chains.
%%====================================================================
%% Internal functions
%%====================================================================
iterate(End, End, MaxN, Max, _LookupTbl) -> {MaxN, Max}; 
iterate(I, End, MaxN, Max, LookupTbl) -> 
    L = chain_length(I, LookupTbl),
    case L > Max of
        true -> 
            iterate(I + 1, End, I, L, LookupTbl);
        _ ->
            iterate(I + 1, End, MaxN, Max, LookupTbl)
    end.

%calculate the chain length of a number
%using a lookup tables to save processing
chain_length(1, _) -> 1;
chain_length(N, LookupTbl) ->
    L = ets:lookup(LookupTbl, N),
    case L of
        [] -> NewN = case N rem 2 of
                         0 -> N div 2;
                         _ -> 3*N + 1
                     end,
              Len = 1 + chain_length(NewN, LookupTbl),
              ets:insert(LookupTbl, {N, Len}),
              Len;
        [{N, Len}] ->
            Len
    end.
